// https://www.lintcode.com/problem/unique-binary-search-trees/

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int numTrees(int n) {
        // write your code here
        if (n == 0) {
          return 1;
        }
        int[] ret = new int[n + 1];
        Arrays.fill(ret, 0);
        ret[0] = 1;
        ret[1] = 1;
        for (int i = 2; i <= n; ++i) {
          for (int j = 1; j <= i; ++j) {
            ret[i] += ret[j - 1] * ret[i - j];
          }
        }
        return ret[n];
    }
}